package hermesV3.services.Space;

import java.util.Collection;
import java.util.Hashtable;

import javax.vecmath.Point3d;

import it.unicam.cs.cosy.bioshape.core.components.exception.NotEnoughSpaceException;

/**
 * A tree data structure where each internal node has exactly eight children.<br>
 * It is useful to partition a three dimensional space by recursively
 * subdividing it into eight octants with the same volume.<br>
 * Each {@link OctreeNode} contains a {@link Point3d} (a 3-dimensional point),
 * which is the "centre" of the subdivision for that {@link OctreeNode}.
 * 
 * @author Alanis Gaston
 * 
 */
public class OctreeNode {

	private double weight;
	private OctreeNode[] children;
	private Point3d[] bounds;
	private final int order[] = new int[] { 0, 7, 1, 6, 2, 5, 3, 4 };
	private int childCard = 0;

	/**
	 * An {@link OctreeNode} with bounds and a weight.
	 * 
	 * @param lowerBounds
	 *            A {@link Point3d} that delimits the Space lower bound
	 * @param upperBound
	 *            A {@link Point3d} that delimits the Space upper bound
	 * @param weight
	 *            The {@link OctreeNode} weight, ranging from 0 to 1
	 */
	public OctreeNode(Point3d lowerBounds, Point3d upperBound, double weight) {
		this.bounds = new Point3d[2];
		this.bounds[0] = lowerBounds;
		this.bounds[1] = upperBound;
		this.weight = weight;
		children = new OctreeNode[8];
	}

	/**
	 * An {@link OctreeNode} with bounds and a weight.
	 * 
	 * @param bounds
	 *            A {@link Point3d} Array that delimits the Space bounds the
	 *            link is defined under the later defined piece.
	 * @param weight
	 *            The {@link OctreeNode} weight, ranging from 0 to 1
	 */
	private OctreeNode(Point3d[] bounds, double weight) {
		this.bounds = bounds;
		this.weight = weight;
		children = new OctreeNode[8];
	}

	/**
	 * Add recursively a leaf to the {@link OctreeNode}.<br>
	 * Each level is filled completely (if possible) before descending through
	 * the tree. The weight assigned to the leaf represents the space fraction
	 * occupied by the leaf itself.
	 * 
	 * @param weight
	 *            the weight of this {@link OctreeNode}, i.e. the volume
	 *            occupied by the {@link OctreeNode} itself
	 * @throws NotEnoughSpaceException
	 *             if all the octree nodes weights sum is higher than 1 or if
	 *             the next level weight is higher than 1
	 */
	public void addElement(double weight) throws NotEnoughSpaceException {
		// if no children yet...
		if (childCard == 0) {
			children[0] = new OctreeNode(this.split(), this.weight * 8);
			childCard++;
		}
		// add the weight of the overall weight of this octree node (8 times)
		if ((this.weight + weight) > 1)
			throw new NotEnoughSpaceException("Octree is Full");
		this.weight += weight;
		double weightNextLevel = weight * 8;
		if (weightNextLevel > 1)
			throw new NotEnoughSpaceException("Octree is Full");
		// if some nodes are free...
		if (childCard < 8) {
			// ...I insert the new weight in the first available child (orderly)
			for (int i = 0; i < 8; i++) {
				if (children[i] == null) {
					children[i] = new OctreeNode(this.split(), weightNextLevel);
					childCard++;
					break;
				}
				if (children[i].weight < weightNextLevel) {
					for (int e = 7; e > i; e--)
						children[e] = children[e - 1];
					children[i] = new OctreeNode(this.split(), weightNextLevel);
					childCard++;
					break;
				}
			}
			return;
		}
		// ...otherwise, if all the branches are full...
		if (children[7].weight == 1)
			throw new NotEnoughSpaceException("Octree is Full");
		// if no empty node, recursively calls addition to the node with less
		// weight
		children[7].addElement(weightNextLevel);
		// reordering of subtree branches
		for (int i = 7; i > 0; i--) {
			if (children[i].weight > children[i - 1].weight) {
				OctreeNode node = children[i];
				children[i] = children[i - 1];
				children[i - 1] = node;
			} else
				break;
		}
	}

	/**
	 * Searches recursively the leaves of the calling node subtree and gets
	 * their centres and their levels. Then these values are put into an
	 * HashTable.<br>
	 * Uses this private Class method {@link #getLeaves(int)}.
	 * 
	 * @return an HashTable.
	 */
	public Hashtable<Point3d, Integer> getLeaves() {
		return getLeaves(0);

	}

	/**
	 * Searches recursively the leaves of the calling node subtree at the input
	 * level.<br>
	 * When a leaf is discovered, its centre and its level are put into an
	 * HashTable. The level is computed through the leaf weight (that is ranging
	 * from 0 to 1).
	 * 
	 * @param inputLevel
	 *            The node subtree level
	 * @return an HashTable.
	 */
	private Hashtable<Point3d, Integer> getLeaves(int inputLevel) {
		int level = inputLevel;
		Hashtable<Point3d, Integer> leaves = new Hashtable<Point3d, Integer>();
		// se sono una foglia
		if (children[0] == null) {
			double app = weight;
			while (app < 1.0) {
				app = app * 8.0;
				level++;
			}
			leaves.put(this.getCenter(), new Integer(level));
			return leaves;
		}
		level++;
		// se sono un nodo richiamo ricorsivamente il metodo
		for (int i = 0; i < 8; i++) {
			if (children[i] == null)
				break;
			leaves.putAll(children[i].getLeaves(level));
		}
		return leaves;
	}

	/**
	 * Gets this node centre.<br>
	 * A centre is a {@link Point3d} which dimensions are the node dimensions
	 * middle points.
	 * 
	 * @return this node centre
	 */
	private Point3d getCenter() {
		Point3d center = new Point3d(bounds[1]);
		center.add(bounds[0]);
		center.x /= 2;
		center.y /= 2;
		center.z /= 2;
		return center;
	}

	/**
	 * Gets this node father bounds and splits them according to the octant.
	 * 
	 * @return the node son centre
	 */
	private Point3d[] split() {
		Point3d lowerBound = new Point3d(bounds[0]);
		Point3d upperBound = new Point3d(bounds[1]);
		switch (order[childCard]) {
		case 0:
			upperBound.setX((lowerBound.getX() + upperBound.getX()) / 2);
			upperBound.setY((lowerBound.getY() + upperBound.getY()) / 2);
			upperBound.setZ((lowerBound.getZ() + upperBound.getZ()) / 2);
			break;
		case 1:
			upperBound.setX((lowerBound.getX() + upperBound.getX()) / 2);
			upperBound.setY((lowerBound.getY() + upperBound.getY()) / 2);
			lowerBound.setZ((lowerBound.getZ() + upperBound.getZ()) / 2);
			break;
		case 2:
			upperBound.setX((lowerBound.getX() + upperBound.getX()) / 2);
			lowerBound.setY((lowerBound.getY() + upperBound.getY()) / 2);
			upperBound.setZ((lowerBound.getZ() + upperBound.getZ()) / 2);
			break;
		case 3:
			upperBound.setX((lowerBound.getX() + upperBound.getX()) / 2);
			lowerBound.setY((lowerBound.getY() + upperBound.getY()) / 2);
			lowerBound.setZ((lowerBound.getZ() + upperBound.getZ()) / 2);
			break;
		case 4:
			lowerBound.setX((lowerBound.getX() + upperBound.getX()) / 2);
			upperBound.setY((lowerBound.getY() + upperBound.getY()) / 2);
			upperBound.setZ((lowerBound.getZ() + upperBound.getZ()) / 2);
			break;
		case 5:
			lowerBound.setX((lowerBound.getX() + upperBound.getX()) / 2);
			upperBound.setY((lowerBound.getY() + upperBound.getY()) / 2);
			lowerBound.setZ((lowerBound.getZ() + upperBound.getZ()) / 2);
			break;
		case 6:
			lowerBound.setX((lowerBound.getX() + upperBound.getX()) / 2);
			lowerBound.setY((lowerBound.getY() + upperBound.getY()) / 2);
			upperBound.setZ((lowerBound.getZ() + upperBound.getZ()) / 2);
			break;
		case 7:
			lowerBound.setX((lowerBound.getX() + upperBound.getX()) / 2);
			lowerBound.setY((lowerBound.getY() + upperBound.getY()) / 2);
			lowerBound.setZ((lowerBound.getZ() + upperBound.getZ()) / 2);
			break;
		}
		return new Point3d[] { lowerBound, upperBound };
	}

	/**
	 * Computes recursively this node subtree deepest level, by descending the
	 * tree until it discovers a leaf.
	 * 
	 * @param tot
	 *            It will contain this node subtree deepest level
	 * 
	 */
	private void getNumberLevels(int[] tot, Collection<Integer> maxLevel) {
		for (int i = 0; i < this.children.length; i++) {
			if (this.children[i] != null) {
				// mi sto abbassando nell'albero
				tot[0]++;
				if (tot[0] > maxLevel.size()) {
					// ho trovato un nodo di un livello piu basso di
					// quelli trovati fino ad ora
					maxLevel.add(new Integer(tot[0]));
				}
				this.children[i].getNumberLevels(tot, maxLevel);
				// mio sto alzando nell'albero
				tot[0]--;
			}
		}
		return;
	}

	/**
	 * Computes recursively this node subtree height.
	 * 
	 * @param maxLevel
	 *            maximal level considered
	 * 
	 * @return this node subtree height
	 */
	public Collection<Integer> getNumberLevels(Collection<Integer> maxLevel) {
		this.getNumberLevels(new int[1], maxLevel);
		maxLevel.add(new Integer(maxLevel.size() + 1));
		return maxLevel;
	}

	/**
	 * Computes this subtree nodes number.
	 * 
	 * @param tot
	 *            it will contain this subtree nodes number
	 */
	public void getNumberNodes(int[] tot) {
		for (int i = 0; i < this.children.length; i++) {
			if (this.children[i] != null) {
				tot[0]++;
				this.children[i].getNumberNodes(tot);
			}
		}
	}

	/**
	 * Computes this subtree leaves number.
	 * 
	 * @param tot
	 *            it will contain this subtree leaves number
	 */
	public void getNumberLeaves(int[] tot) {
		int sum = 0;
		for (int i = 0; i < this.children.length; i++) {
			if (this.children[i] != null)
				this.children[i].getNumberLeaves(tot);
			else
				sum++;
		}
		if (sum == this.children.length)
			tot[0]++;
	}

	/**
	 * @return the weight
	 */
	public double getWeight() {
		return weight;
	}

	/**
	 * Sets this node weight.
	 * 
	 * @param weight
	 *            the weight for the tree
	 */
	public void setWeight(double weight) {
		this.weight = weight;
	}
}